1. Technical Field
Example embodiments of the present invention relates in general to a distributed video encoder and decoder and a distributed video decoding method and more specifically to a distributed video encoder and decoder and a distributed video decoding method using an adaptive quantization.
2. Description of the Related Art
Digital video data used in video conferences, video on demands (VODs), digital broadcasting receivers, and cable televisions (CATVs) commonly has a large amount of data, and thus it is not used “as is” but compressed by an efficient compression technique.
Examples of representative video compression techniques include MPEG-4 video coding and MPEG-4 AVC/H.264. The techniques are usually employed in video players, VODs, video conferences, digital multimedia broadcasting (DMB). Due to the development of wireless communication such as 2.5 G and 3 G communications, the techniques are recently employed for video transmission in wireless mobile environments.
In order to compress digital video data, a method of reducing temporal redundancy, a method of reducing spatial redundancy, and method of reducing statistical redundancy of generated codes are usually used. The method of reducing temporal redundancy is a motion estimation and compensation technique.
Existing coding techniques remove temporal redundancy to achieve high coding efficiency. However, since a part which occupies the highest computation cost in a moving picture encoder is the motion estimation and compensation technique, it is very important to reduce complexity of the encoder in a limited source environment such as a sensor network.
A distributed source coding (DSC) technique based on a Slepian-Wolf theorem is highlighted as one of methods of resolving the complexity problem of the encoder. The Slepian-Wolf theorem mathematically proved that even though correlated sources are separately encoded, if the encoded data are jointly decoded, a coding gain of up to the same degree as that obtained by predictive-coding the respective sources together can be obtained.
A distributed video coding (DVC) technique is one which the distributed source coding technique of lossless compression is expanded to a case of lossy compression and is based on a Wyner-Ziv theorem in which the Slepian-Wolf theorem which is a theoretical base of the distributed source coding technique is expanded to a case of lossy compression.
From a point of view of a video coding technique, it is meant that, in both techniques, processing such as motion estimation and compensation performed to reduce inter-picture redundancy can be implemented in a decoder side without any coding gain loss.
The distributed video coding technique is described in Anne Aaron, Shantanu Rane, Rui Zhang, Bernd Girod, “Wyner-Ziv Coding for Video: Applications to Compression and Error Resilience,” Proc., IEEE Data Compression Conference (DCC '03), pp. 93-102, 2003. In the distributed video coding technique, a decoder uses similarity between neighboring pictures to generate side information for a current picture. The side information is regarded as what noise of a virtual channel is added to the current picture which has to be reconstructed, and the current picture is reconstructed by removing the noise in the side information using a channel code transmitted from an encoder.
FIG. 1 is a block diagram illustrating a configuration of an encoder 110 and a decoder 130 according to the conventional Wyner-Ziv coding technique.
As illustrated in FIG. 1, the encoder 110 according to the conventional Wyner-Ziv coding technique includes a block unit dividing unit 111, a quantization unit 112, a channel code encoding unit 113, and a key picture encoding unit 114. The decoder 130 includes a channel decoding unit 131, a video reconstruction unit 132, a key picture decoding unit 133, and a side information generating unit 134.
The encoder 110 according to the Wyner-Ziv coding technique classifies pictures to be encoded into two types. One is a picture (hereinafter, referred to as a “WZ picture”) which is Wyner-Ziv coded using channel code encoding, and the other is a picture (hereinafter, referred to as a “key picture”) which is encoded by a conventional coding technique such as H.264/MPEG-4 AVC.
The key picture encoding unit 114 encodes key pictures by a predetermined method selected by a user such as intra picture coding of H.264/MPEG-4 AVC and transmits the encoded key pictures to the decoder 130.
The key picture decoding unit 133 of the decoder 130 reconstructs the key picture which has been encoded by a predetermined method, and the side information generating unit 134 generates side information corresponding to the WZ picture using the key picture reconstructed by the key picture decoding unit 133.
The side information generating unit 134 generates the side information corresponding to the WZ picture to be reconstructed by using an interpolation technique of assuming a linear motion between pictures located before and after the WZ picture.
In order to encode the WZ picture, the block unit dividing unit 111 of the encoder 110 divides the input WZ picture into predetermined coding units. The quantization unit 112 performs quantization of coding units divided by the block unit dividing unit 111. The channel code encoding unit 113 generates parity bits for quantized values using a channel code. The generated parity bits are stored in a parity buffer (not illustrated) and then sequentially transmitted according to a request of the decoder 130 through a feed-back channel.
The channel code decoding unit 131 of FIG. 1 receives the parity bits transmitted from the encoder 110 to estimate the quantized values. The video reconstruction unit 132 of FIG. 1 receives the quantized values estimated by the channel code decoding unit 131 and dequantizes or inverse-quantizes the quantized values to reconstruct the WZ picture.
Ambiguity occurring at the time of dequantization can be resolved with reference to the side information input from the side information generating unit 134. This is described in detail in Anne Aaron, Shantanu Rane, Rui Zhang, Bernd Girod, “Wyner-Ziv Coding for Video: Applications to Compression and Error Resilience,” Proc., IEEE Data Compression Conference (DCC '03), pp. 93-102, 2003.
FIG. 2 is a block diagram illustrating a configuration of the channel code decoding unit 131 according to the Wyner-Ziv coding technique.
As illustrated in FIG. 2, the channel code decoding unit 131 includes soft-input soft-out (SISO) decoding units 210a and 210b, channel probability value computing units 211a and 211b, interleavers 213a and 213b, de-interleavers 214a and 214b, a DEMUX 215, and a determination unit 216.
Parity bit data which includes the parity bits for the quantized values transmitted from the encoder 110 and parity bits for values obtained by interleaving the parity bits is divided by the DEMUX 215 into two and input to the channel probability value computing units 211a and 211b, respectively.
Each of the channel probability computing units 211a and 211b receives a probability statistical characteristic for side information and noise, and the parity bits transmitted from the encoder 110 to compute a channel probability value.
Each of the SISO decoding units 210a and 210b performs decoding based on the channel probability value and A Priori Probability (APrP) value received from the other SISO decoding unit 210a or 210b. Each of the SISO decoding units 210a and 210b computes a forward state matrix from a transition matrix while proceeding from an initial state to a last state on a trellis and a backward state matrix while proceeding in an opposite direction when it arrives at the last state. A Posteriori Probability (APoP) value and an extrinsic probability value are computed using the state matrix value and the transition matrix value.
The determination unit 216 computes an error rate using the APoP value. When the error rate is equal to or less than a threshold value, decoding is finished, while when the error rate is more than the threshold value, the other SISO decoding unit 210a or 210b repeats the above-described process. However, when the error rate is not equal to or less than the threshold value even after repeating the process, the decoder 130 may request the encoder 110 to provide additional parity data through the feed-back channel.
FIG. 3 is a block diagram illustrating another configuration of the channel code decoding unit 131 according to the Wyner-Ziv coding technique of FIG. 1.
As illustrated in FIG. 3, a low density parity check code (LDPC) channel code decoder 300 includes a log likelihood ratio (LLR) computing unit 301 and an LDPC decoding unit 302. The LDPC was invented by Robert Gallager at MIT in 1963, and is an error correction code which has a low density check matrix since the number of 1 s in a check matrix of a code is smaller than a length of a code word, is very close to a theoretical limit of Shannon, and has excellent coding performance.
A belief propagation (BP) algorithm may be used for LDPC decoding. Side information, parity data and channel error estimation information for the side information are needed for LDPC decoding. The side information is information having similarity to original information and input to the LLR computing unit 301 and the LDPC decoding unit 302.
The parity data is information which is generated by LDPC channel coding by using the original information as an input and input to the LDPC decoding unit 302 of the LDPC channel code decoder 300. The channel error estimation information for the side information represents how much the side information is similar to the original information by using a numerical method and is input to the LLR computing unit 301. The LDPC channel code decoder 300 receives the inputs, and finally decodes and outputs quantized WZ picture data.
The channel error estimation information for the side information may be expressed by a conditional probability P(X=0|Y=y) or P(Y=1|Y=y) in which a value to be channel-decoded is to be “0” or “1” when the side information is given as a conditional event. Here, Y denotes the side information, and X denotes a value to be channel-decoded. The conditional probability value is needed for computation of an LLR value and thus is input to the LDPC channel code decoder 300 as the channel code estimation information for the side information. The LLR value may be computed using the conditional probability value as in Equation 1. Of course, the LLR value may be computed by a method other than Equation 1.
                              L          ⁢                                          ⁢          L          ⁢                                          ⁢          R                =                  log          ⁢                                                    P                ⁡                                  (                                      X                    =                                                                  0                        |                        Y                                            =                      y                                                        )                                                            P                ⁡                                  (                                      X                    =                                                                  1                        |                        Y                                            =                      y                                                        )                                                      .                                              Equation        ⁢                                  ⁢        1            
When the LLR value computed by Equation 1 is zero, it is very difficult to determine whether a bit of X is 0 or 1. When the LLR value is a positive value, a probability that X will be 0 is high, while when the LLR value is a negative value, a probability that X will be 1 is high.
FIG. 4 is a view illustrating an operation of the quantization unit 112 according to the Wyner-Ziv coding technique.
A conventional quantization method according to the Wyner-Ziv coding technique performs the same quantization on all areas of a given image. Typically, an image is divided in blocks, quantization by the same strength is performed for the respective blocks, and the quantized blocks are processed in units of bit planes. FIG. 4 two-dimensionally represents the quantization result using a block index which identifies a block in a given image and a bit plane index which identifies a bit plane. Quantization may be applied to pixel values or coefficients generated by a predetermined transform such as discrete cosine transform (DCT). In FIG. 4, a block index means an index which indicates blocks configured by pixels when transform is not performed and an index which indicates blocks configured by transform coefficients when transform is performed (blocks in which transform is performed are not illustrated in FIG. 4). Colored quadrangles represent bits, which are to be transmitted, which will not be discarded after quantization, and non-colored quadrangles represent bits which correspond to information to be discarded after quantization. A portion defined by a dotted line represents a channel coding message which is configured by bits of respective blocks to be channel-coded. As illustrated in FIG. 4, the conventional quantization method has a problem in that quantization by the same strength is applied to all areas of a given image and thus the respective bit planes are the same in number of bits to be transmitted. This is to use a channel coding method of the same code rate in all bit planes to be encoded.
However, since areas in an image of an actual video signal are different in statistical characteristic, when quantization by the same strength is performed for an overall given image as in the conventional method, coding performance deteriorates. For example, this is because a certain area in an image which needs to be encoded may be an object in which a motion is large, but a large number of static areas may be included.